package main

import (
	"fmt"
	"math"
)

func main() {
	res := f1(3)
	fmt.Println(res)

}


func countNumbersWithUniqueDigits(n int) int {
	list := make([]int,10)
	if n == 0 {
		return 1
	}
	if n == 1 {
		return 10
	}

	list[0] = 1
	list[1] = 9
	sum  := list[0]+list[1]
	for  i := 2; i <= int(math.Min(float64(n),10)); i++{
		// 由n-1位直接求出n位时的数量
		list[i] = list[i-1] * (10 - (i-1))
		sum += list[i]
	}

	return sum
}



//n=2
//区分首位以0开始, 以0开始相当于dp[n-1]
//dp[0] = 1
//dp[1] = (dp[0] + 9) = 10
//dp[2] = dp[1]  +  9 * 9 =  dp[1] + 9 * A(9,1) =  91
//dp[3] = dp[2]  +  9 * 9 * 8 = dp[2] + 9 * A(9, 2) = 739
//dp[4] = dp[4]  +  9 * 9 * 8 * 7

//dp[0] = 1
//dp[1] = 10
//i >= 2 ==> dp[i] = dp[i-1] + 9 * A(9,i-1)
func f1(n int) int  {
	list := make([]int,10)
	if n == 0{
		return 1
	}
	if n == 1{
		return 10
	}
	list[0] = 1
	list[1] = 9
	sum := list[0]+list[1]
	for i := 2 ; i <= int(math.Min(float64(n),10));i++{
		list[i] = list[i-1]*(10-(i-1))
		sum += list[i]
	}

	return sum
}

